/**
 * 项目名称: Topic_95.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月24日07时37分48秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 暴力卡住 8
//class Solution {
//public:
//    vector<TreeNode*>ans;
//    vector<vector<int>>vn;
//    vector<vector<int>>ve;
//    vector<int>init;
//    bool st[10];
//    void pre(int n){
//        if(init.size() == n){
//            TreeNode * root= nullptr;
//            for(auto y:init) {
//                createTree(root, y);
//            }
//            vector<int>pl;
//            ino(root,pl);
//            bool flag = false;
//            for(auto p:ve){
//                if(p == pl)flag = true;
//            }
//            if(!flag) {
//                ve.push_back(pl);
//                ans.emplace_back(root);
//            }
//            return;
//        }
//        for(int i = 1;i<=n;i++){
//            if(!st[i]){
//                st[i]=true;
//                init.push_back(i);
//                pre(n);
//                st[i]= false;
//                init.pop_back();
//            }
//        }
//    }
//
//    void createTree(TreeNode *&T,int k){
//        if(!T){
//            T= new TreeNode;
//            T->val = k;T->left = T->right = nullptr;
//        }
//        else if(k<T->val) createTree(T->left,k);
//        else if(k>T->val)createTree(T->right,k);
//    }
//
//    void ino(TreeNode* root,vector<int>&num){
//        if(root){
//            num.push_back(root->val);
//            ino(root->left,num);
//            ino(root->right,num);
//        }
//        else num.push_back(0);
//    }
//
//    vector<TreeNode*> generateTrees(int n) {
//        if(n==0)return ans;
//        pre(n);
//        return ans;
//    }
//};

class Solution {
public:
    vector<TreeNode*>generateTrees(int start,int end){
        if(start > end)return {nullptr};
        vector<TreeNode*>allTrees;
        //枚举可行根节点
        for(int i = start;i<=end;i++){
            // 获得所有可行的左子树集合
            vector<TreeNode*>leftTrees = generateTrees(start,i-1);
            // 获得所有可行的右子树集合
            vector<TreeNode*>rightTrees = generateTrees(i+1,end);

            //从左子树集合中选出一颗右子树,从右子树集合中选出一颗右子树,拼接到根节点
            for(auto &left:leftTrees)
                for(auto &right:rightTrees){
                    TreeNode* currTree = new TreeNode(i);
                    currTree->left = left;
                    currTree->right = right;
                    allTrees.emplace_back(currTree);
                }
        }
        return allTrees;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(!n)return {};
        return generateTrees(1,n);
    }
};